1) Field of the Invention
The present invention relates to an apparatus of and a method for drawing three-dimensional graphics, and more specifically, to rasterization of triangles.
2) Description of the Related Art
A conventional computer graphics drawing apparatus has the following configuration. FIG. 48 is a block diagram of the configuration of a conventional real-time computer graphics (CG) drawing apparatus. The conventional drawing processing apparatus mainly includes a vertex input processor 2901 that inputs vertex data on a triangle, a vertex operational processor 2902 that operates the vertex data input from the vertex input processor 2901, a rasterizer 2903 that generates pixel data from the vertex data processed by the vertex operational processor 2902, a pixel processor 2907 that operates the pixel data generated by the rasterizer 2903, a vertex buffer 2906 that buffers the vertex data input from the vertex operational processor 2902, and a drawing memory 2908 that stores the pixel data processed by the pixel processor 2907.
The rasterizer 2903 includes a setup processor 2904 that acquires data on three vertices of the triangle from the vertex data buffer 2906, and that generates setup data necessary for rasterization, and a traverser 2905 that generates the pixel data using the setup data received from the setup processor 2904.
The vertex data input to the rasterizer 2903 is organized by vertex coordinates such as homogeneous coordinates and window coordinates, and vertex parameters such as colors, a fog, texture coordinates, and normal vectors. Using the vertex data, the rasterizer 2903 carries out a processing for detecting pixels inside of the triangle, and a processing for calculating pixel parameters, and generates the pixel data. The pixel data is organized by widow coordinates, a depth, a color, a fog, texture coordinates, normal vectors, and a flag representing whether a pixel is inside of the triangle.
Normally, the rasterizer 2903 expresses a shape of the triangle by linear equations for three sides as the following equations (1):A0(X, Y)=a0·(X−X0)+b0·(Y−Y0)A1(X, Y)=a1·(X−X1)+b1·(Y−Y1)A2(X, Y)=a2·(X−X2)+b2·(Y−Y2)   (1 )where X and Y denote the window coordinates, (X0, Y0), (X1, Y1), (X2, Y2) denote the window coordinates of vertices of the triangle, respectively, and a0, a1, a2, b0, b1, and b2 denote constants. These linear equations are called edge functions, which are used to classify the pixels on a display into three regions of the triangle, inside, on sides, and outside.
Namely, if values of the edge functions are greater than zero, a pixel is inside the triangle. If the values of the edge are just zero, the pixel is on a side of the triangle. If the values of the edge functions are smaller than zero, the pixel is outside the triangle. The rasterizer 2903 determines whether values of the edge functions of the three sides are all greater than zero, thereby determining whether the pixel is inside the triangle. Gradients a0, b0, a1, b1, a2, and b3 of the edge functions are calculated by the following equations (2):a0=Y0−Y1b0=X1−X0a1=Y1−Y2b1=X2−X1a2=Y2−Y0b2=X0−Y2  (2)
As a method for incorporating these calculation procedures in hardware, a method using a digital differential analyzer (DDA) and a method based on direct evaluation (DE) are known.
With the DDA method, only initial values of the edge functions of a typical pixel are calculated by equation (1), and the gradients of the edge functions are sequentially added to the respective initial values, thereby calculating edge functions of adjacent pixels.
Since the DDA method is required to perform only addition except for the calculation of the initial values, a circuit area of the drawing processing apparatus can be reduced. With the DDA method, however, it is necessary to consider errors resulting from accumulation of addition. In the rasterizer 2903, the setup processor 2904 calculates the initial values and the gradients, and the traverser 2905 adds the gradients to the respective initial values.
With the DE method, the edge functions of all pixels are calculated by equation (1). Therefore, if the DE method is used, it is unnecessary to consider errors, differently from the DDA method. However, because of the frequent use of multiplication, the circuit area of the processing apparatus is increased. In the rasterizer 2903, the setup processor 2905 calculates the gradients, and the traverser 2905 performs multiplication using equation (1).
The rasterizer 2903 calculates the parameters, such as the depth, the color, the fog, the texture coordinates, and the normal vectors, for each of the pixels determined to be inside the triangle. These parameters are calculated by interpolating the parameters for the three vertices of the triangles. As an interpolation calculation method, two methods are known: a method using the DDA and a method using barycentric coordinates β.
With the DDA method, initial values of the parameters for the typical pixel (X, Y) are calculated by the following equation (3):P(X, Y)=a·X+b·Y+c.  (3)
By sequentially adding the gradients a and b to the respective initial values, parameters for adjacent pixels are calculated. The coefficients a, b, and c in equation (3) are calculated by the following equations (4):a·X0+b·Y0 +c=p0a·X1+b·Y1+c=p1a·X2+b·Y2+c=p2  (4)where (X0, Y0), (X1, Y1), and (X2, Y2) are window coordinates of the three vertices of the triangles, and p0, p1, and p2 are corresponding vertex parameters. Similarly to the edge functions, the DDA method is required to perform only addition except for the calculation of the initial values. Therefore, an operational circuit can be made small in size. It is, however, necessary to consider errors resulting from accumulation of the addition. Further, the coefficients a, b, and c need to be calculated by equation (4) by as much as the number of parameters. If the number of parameters is large, a calculation volume is disadvantageously increased. In the rasterizer 2903, the setup processor 2905 calculates the initial values and the gradients, and the traverser 2905 adds the gradients to the respective initial values.
With the method using the barycentric coordinates β, all the parameters can be interpolated using the following equation (5):P(X, Y)=s0·p0+s1·p1+s2·p2  (5)
With this method, even if the parameters are changed, the parameters can be interpolated using the barycentric coordinates β0, β2, and β2. Therefore, the method using the barycentric coordinates β is effective if the number of parameters is large. The barycentric coordinates β0, β1, and β2 are calculated by the following equations (6):β0(X, Y)=(1/sum(X, Y))·A0(X, Y)β1(X, Y)=(1/sum(X, Y))·A1(X, Y)β2(X, Y)=(1/sum(X, Y))·A2(X, Y)1/sum(X, Y)=1/(A 0(X, Y)+A1(X, Y)+A2(X, Y))  (6)
In the rasterizer 2903, the traverser 2905 performs calculations of equation (6) and calculates the barycentric coordinates of the respective pixels. Either the traverser 2905 or the pixel processor 2907 connected in rear of the rasterizer 2903 perform calculations of equation (5).
Using one of these methods, the rasterizer 2903 carries out the processing for determining whether each pixel is inside the triangle, and the processing for interpolating the vertex parameters and calculating the parameters for the respective pixels.
As can be seen, according to the conventional art, the processing for determining whether each pixel is inside the triangle and the processing for interpolating the vertex parameters and calculating the pixel parameters are carried out. These processings are carried out using the window coordinates of the vertices of a drawing primitive. To do so, the vertex operational processor 2902 projects the vertices on a window, and transmits the window coordinates on which the vertices are projected on the window to the rasterizer 2903.
However, the vertex data on the triangle input to the rasterizer 2903 often include data on the vertex for which a W component of view coordinates is smaller than zero, that is, data indicating that a part of the triangle is behind a point of view. If the triangle includes the vertex located behind the point of view, the vertex is not projected onto the window and does not, therefore, include window coordinates. Considering this, if such a triangle is to be rasterized, as shown in FIG. 32, the triangle is cut on a near clip plane into a part 3201 which is projected onto a view port and a part 3202 which is not projected onto the view port in advance. The rasterizer 2903 inputs window coordinates of the part 3201 projected onto the window. The processing for dividing the drawing primitive on the clip plane is referred to as “clipping”. Since the clipping is complicated and large in processing amount, it is normally carried out using dedicated hardware. However, U.S. Pat. No. 6,504,542 discloses a rasterization processing technique which can dispense with the clipping.
Nevertheless, in order to adopt the conventional rasterization processing, a new processing for efficiently searching for a scan starting point is necessary. For this reason, if a part of the triangle is behind the point of view, the drawing processing apparatus is required to carry out a special processing such as the processing for searching for the scan starting point besides the processings carried out if all regions of the triangle are projected onto the window, i.e., a projection plane. Processing efficiency is thereby disadvantageously deteriorated.